﻿#define _CRT_SECURE_NO_WARNINGS 1



#include "SList.h"




// 动态顺序表存在的问题，不带头结点的单链表初步，OJ链表面试题,2反转链表






//2.4 顺序表的问题及思考
//
// 
// 顺序表的缺陷
// 
// 问题：
//
// 1. 中间 / 头部的插入删除，需要挪动数据，效率低下，时间复杂度为O(N)
// 
// 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗（尤其是异地扩容）。
// 
// 3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。
//		例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
// 
// 
// 
// 
// 
// 
// 
//思考：如何解决以上问题呢？下面给出了链表的结构来看看。
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 3.链表
// 
// 
//
// 3.1 链表的概念及结构
//
// 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
//		 中的指针链接次序实现的 。
// 
// 
//     单独一块的空间叫做节点/结点
// 
// 
// 
// 
// 

//void TestSList1()
//{
//
//	// 堆区
//	STLNode* n1 = malloc();
//	STLNode* n2 = malloc();
//	n1->next = n2;
//	// 节点所在内存空间必须要在堆上。可以动态开辟和释放销毁
//	// malloc free 跟堆进行交互
//
//
//
//	// 栈帧
//	SLTNode n1;
//	SLTNode n2;
//	n1.next = &n2;
//
//
//}
// 
//
// 链表逻辑结构：想象出来的样子
//
//  
// 链表物理结构：实际存储的样子 
// 
// 
//
//void TestSList1()
//{
//	//// 单独创建每个节点
//	//SLTNode* n1 = BuySLTNode(1);
//	//SLTNode* n2 = BuySLTNode(2);
//	//SLTNode* n3 = BuySLTNode(3);
//	//SLTNode* n4 = BuySLTNode(4);
//
//	//// 节点链接
//	//n1->next = n2;
//	//n2->next = n3;
//	//n3->next = n4;
//	//n4->next = NULL;
//
//
//	// 创建10个节点的链表
//	SLTNode* plist = CreateSList(5);
//
//	// 打印这个链表的所有数据
//	SLTPrint(plist);
//
//}


//int main()
//{
//	TestSList1();
//
//	return 0;
//}
// 
// 
// 
// 
// 
// 注意：
// 
// 链表的关键在于 头指针
// 
// 结构体的关键在于 结构
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 3.2链表的分类
// 
// 
// 1.单向或者双向
// 
// 2.带头或者不带头
// 
// 3.循环或者非循环
// 
// 
// 
// 
// 
// 单向不带头链表
// 
// 

//void TestSList1()
//{
//	SLTNode* plist = CreateSList(5);
//	SLTPrint(plist);
//}
//



// 
//void TestSList2()
//{
//	SLTNode* plist = CreateSList(5);
//	
//	// 尾插
//	SLTPushBack(plist, 100);
//	SLTPushBack(plist, 200);
//	SLTPushBack(plist, 300);
//
//	SLTPrint(plist);
//}





// 顺序表为空，size == 0 ，数据为零及为空。capicity != 0可能不为空，空间不为零
// 链表为空，plist == NULL 为空
// 
// 
// 函数栈帧 ：
//		需要改变int    需要传实参int*
//		需要改变int*   需要传实参int**
//		需要改变int**  需要传实参int***
//
void TestSList3()
{
	SLTNode* plist = NULL;

	// 尾插
	// 这里传入plist 指针变量的地址，使用二级指针
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);

	SLTPrint(plist);




	// 尾删
	SLTPopBack(&plist);
	SLTPrint(plist);
	
	SLTPopBack(&plist);
	SLTPrint(plist);
	
	SLTPopBack(&plist);
	SLTPrint(plist);
	
	SLTPopBack(&plist);
	SLTPrint(plist);
}

int main()
{
	//TestSList1();
	//TestSList2();
	TestSList3();


	return 0;
}
// 
// 
// 
// 
// 
// 
// 
// 
// 
// 3.4 链表面试题
// 
// 1. 删除链表中等于给定值 val 的所有结点。
//		https://leetcode-cn.com/problems/remove-linked-list-elements/description/
// 
// 2. 反转一个单链表。
//		https://leetcode-cn.com/problems/reverse-linked-list/description/
// 
// 思路1：取节点头插


struct ListNode* reverseList(struct ListNode* head){
struct ListNode* cur = head;
struct ListNode* rhead = NULL;

while (cur)
{
	// 保存下一个需要逆置的节点
	struct ListNode* next = cur->next;

	// 头插
	cur->next = rhead;
	rhead = cur;

	// 更新需要逆置的节点
	cur = next;
}
// 返回逆置后的链表
return rhead;
}


// 
// 思路2：三个指针翻转
// 
// 
// 
// 
// 3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
//		https://leetcode-cn.com/problems/middle-of-the-linked-list/description/
// 
// 4. 输入一个链表，输出该链表中倒数第k个结点。
//		https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
// 
// 5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。
//		https://leetcode-cn.com/problems/merge-two-sorted-lists/description/
// 
// 6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。
//		https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
// 
// 7. 链表的回文结构。
//		https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
// 
// 8. 输入两个链表，找出它们的第一个公共结点。
//		https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/
// 
// 9. 给定一个链表，判断链表中是否有环。
//		https://leetcode-cn.com/problems/linked-list-cycle/description/
// 
// 
// 
//
